// *****************************************************************************
// Filename:    elevator-control.cc
// Date:        2012-07-04 09:53
// Author:      Guangda Lai
// Email:       lambda2fei@gmail.com
// Description: TODO(laigd): Put the file description here.
// *****************************************************************************

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#include "subset-enumeration.h"

using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::ifstream;
using std::map;
using std::ofstream;
using std::set;
using std::string;
using std::vector;

struct FloorInfo {
  int floor, num_people;
  FloorInfo(int f, int n) : floor(f), num_people(n) {}
};

unsigned int GetElevatorPlan(const unsigned int num_stops,
                             const unsigned int up_cost,
                             const unsigned int down_cost,
                             vector<unsigned int> *target_floors,
                             vector<int> *plan) {
  // Validation.
  for (vector<unsigned int>::const_iterator it = target_floors->begin();
       it != target_floors->end(); ++it) {
    if (*it == 0) {
      cerr << "Invalid input!" << endl;
    }
  }

  if (plan != NULL) plan->clear();
  std::sort(target_floors->begin(), target_floors->end());
  if (target_floors->back() == 1) return 0;

  int valid_start = 0;
  while (target_floors->at(valid_start) == 1 &&
         valid_start < target_floors->size()) {
    valid_start++;
  }

  vector<FloorInfo> floor_info;
  floor_info.push_back(FloorInfo(target_floors->at(valid_start), 1));
  for (int i = valid_start + 1; i < target_floors->size(); ++i) {
    if (floor_info.back().floor == target_floors->at(i)) {
      ++floor_info.back().num_people;
    } else {
      floor_info.push_back(FloorInfo(target_floors->at(i), 1));
    }
  }
  const int num_floor = floor_info.size();
  if (num_stops >= num_floor) return 0;

  // Auxiliary information.
  vector<int> sum_people(floor_info.size());
  sum_people[0] = floor_info[0].num_people;
  for (int i = 1; i < floor_info.size(); ++i) {
    sum_people[i] = sum_people[i - 1] + floor_info[i].num_people;
  }

  // @head[i] is the cost for people whose target floor is lower or equal to
  // floor_info[i].floor to walk from floor_info[0].floor to their targets.
  vector<int> head(floor_info.size());
  int lowest_floor = floor_info[0].floor;
  head[0] = 0;
  for (int i = 1; i < floor_info.size(); ++i) {
    int diff_floor = floor_info[i].floor - lowest_floor;
    head[i] = head[i - 1] + floor_info[i].num_people * diff_floor * up_cost;
  }

  // @tail[i] is the cost for people whose target floor is higher or equal to
  // floor_info[i].floor to walk from the highest possible floor to their
  // targets.
  vector<int> tail(floor_info.size());
  int highest_floor = floor_info.back().floor;
  tail[floor_info.size() - 1] = 0;
  for (int i = floor_info.size() - 2; i >= 0; --i) {
    int diff_floor = highest_floor - floor_info[i].floor;
    tail[i] = tail[i + 1] + floor_info[i].num_people * diff_floor * down_cost;
  }

  // It can be proved that in the optimum plan, the elevator always stops at
  // a subset of the target floors.
  // f[i][j] is the minimum cost for the first j floors when we stop at i floors
  // with the last floor stopped at floor j. We can use rolling arrays to save
  // memory when a plan is not required.
  vector<vector<int> > mid_data;
  if (plan == NULL) {
    mid_data.resize(2);
  } else {
    mid_data.resize(num_stops);
  }
  for (int i = 0; i < mid_data.size(); ++i) {
    mid_data[i].resize(num_floor);
  }

  typedef vector<int> *vptr;
  vptr f = &mid_data[0], g = &mid_data[1];

  // Initial condition.
  f->at(0) = 0;
  for (int j = 1; j < num_floor; ++j) {
    int diff = floor_info[j].floor - floor_info[j - 1].floor;
    f->at(j) = f->at(j - 1) + sum_people[j - 1] * diff * down_cost;
  }

  // Enumerate the number of stops we used.
  for (int i = 2; i <= num_stops; ++i) {
    if (plan == NULL) {
      vptr tmp = f;
      f = g;
      g = tmp;
    } else {
      g = f;
      f = &mid_data[i - 1];
    }
    vector<int> &fr = *f, &gr = *g;
    fr[i - 1] = gr[i - 2];

    // The elevator stops at floor floor_info[j].floor at the ith time.
    for (int j = i; j < num_floor; ++j) {
      // If the elevator stops at floor floor_info[j - 1].floor at the (i-1)th
      // time.
      fr[j] = gr[j - 1];

      // Enumerate the (i-1)th stopping floor. The lowest possible stopping
      // floor is floor_info[i - 2].floor.
      for (int k = i - 2; k < j - 1; ++k) {
        int mid = up_cost * floor_info[j].floor;
        mid += down_cost * floor_info[k].floor;
        mid /= up_cost + down_cost;

        int diff_low_k = floor_info[k].floor - lowest_floor;
        int diff_j_high = highest_floor - floor_info[j].floor;
        int sum_k_mid = sum_people[mid] - sum_people[k];
        int sum_mid_j = sum_people[j - 1] - sum_people[mid];
        int cost_between_kj =
            head[mid] - head[k] - sum_k_mid * diff_low_k * up_cost +
            tail[mid + 1] - tail[j] - sum_mid_j * diff_j_high * down_cost;
        int cur_cost = gr[k] + cost_between_kj;
        if (cur_cost < fr[j]) fr[j] = cur_cost;
      }
    }
  }
  int min_cost = f->at(num_floor - 1);
  for (int i = num_stops - 1; i < num_floor - 1; ++i) {
    int diff_low_i = floor_info[i].floor - lowest_floor;
    int sum_i_top = sum_people[num_floor - 1] - sum_people[i];
    int cur_cost = f->at(i) + head[num_floor - 1] - head[i] -
        sum_i_top * diff_low_i * up_cost;
    if (cur_cost < min_cost) min_cost = cur_cost;
  }

  return min_cost;
}

class AnswerChecker {
 public:
  int result;

  AnswerChecker(const vector<int> *t,
                const int u,
                const int d,
                vector<int> *p)
      : target_floors(t),
        up_cost(u),
        down_cost(d),
        result(~(0U) >> 1),
        plan(p) {
    plan->reserve(target_floors->size());
  }

  void operator()(const vector<int> &subset) {
    int cost = 0, idx = 0;
    for (int i = 0; i < target_floors->size(); ++i) {
      while (target_floors->at(i) > subset[idx] && idx < subset.size()) ++idx;
      if (idx == subset.size()) {
        for (int j = i; j < target_floors->size(); ++j) {
          cost += (target_floors->at(j) - subset.back()) * down_cost;
        }
        break;
      }
      if (target_floors->at(i) == subset[idx]) continue;
      if (idx == 0) {
        cost += (subset[0] - target_floors->at(i)) * up_cost;
      } else {
        cost += std::min((subset[idx] - target_floors->at(i)) * up_cost,
                         (target_floors->at(i) - subset[idx - 1]) * down_cost);
      }
    }
    if (cost < result) {
      result = cost;
      if (plan != NULL) {
        std::copy(subset.begin(), subset.end(), plan->begin());
      }
    }
  }

 private:
  const vector<int> *target_floors;
  const int up_cost;
  const int down_cost;
  vector<int> *plan;
};

int TestOneCase(const int num_stops,
                const int up_cost,
                const int down_cost,
                vector<int> *target_floors) {
  static int test_num = 0;
  test_num++;
  cout << "Testing case #" << test_num << "..." << endl;

  vector<int> plan1, plan2;
  int actual_value = GetElevatorPlan(1, 1, 1, target_floors, &plan1);

  std::sort(target_floors->begin(), target_floors->end());

  vector<int> floors(target_floors->back());
  for (int i = 0; i < floors.size(); ++i) {
    floors[i] = i + 1;
  }

  AnswerChecker checker(target_floors, up_cost, down_cost, &plan2);
  ForEachSubset(floors, num_stops, &checker);

  if (checker.result != actual_value) {
    cerr << "Wrong answer!" << endl;
    cerr << "Expected: " << checker.result << endl;
    cerr << "Actual: " << actual_value << endl;
    exit(1);
  }
}

int Test() {
  vector<int> target_floors, plan;
  target_floors.push_back(10);
  TestOneCase(1, 1, 1, &target_floors);  // #1

  target_floors.push_back(5);
  TestOneCase(1, 1, 1, &target_floors);  // #2

  TestOneCase(2, 1, 1, &target_floors);  // #3

  TestOneCase(1, 3, 1, &target_floors);  // #4
}

int main(int argc, char **argv) {
  Test();
  return 0;
}
